package com.buddy.learn.algorithm.simple;

import java.util.ArrayList;

/**
 * @author Buddy
 * @date 2021/5/17
 */
public class _找出数组中最小的k个元素 {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            if(k>input.length){
                return new ArrayList();
            }
            quitSort(input,0,input.length-1);
            ArrayList<Integer> res = new ArrayList<>();
            for(int i=0;i<k;i++){
                res.add(input[i]);
            }
            return res;
        }

        public void quitSort(int[] arr,int start,int end){
            if(start > end){
                return;
            }
            int pos = partation(arr,start,end);
            quitSort(arr,0,pos-1);
            quitSort(arr,pos+1,end);
        }

        public int partation(int[] arr,int startIndex,int endIndex){
            int left = startIndex;
            int right = endIndex;
            int posVal = arr[left];
            while(left != right){
                while(left<right && arr[right] >posVal){
                    right--;
                }
                while(left<right && arr[left]<=posVal){
                    left++;
                }

                if(left<right){
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            }
            arr[startIndex]=arr[left];
            arr[left] = posVal;
            return left;
        }
    }
